package com.hl.algor_data_struct.sort;

import java.util.Arrays;

/**
 * Created by yuanhailong on 2021/10/24.
 * 归并排序
 *     分而治之的思想
 *     分：将数组一直分解，一直到分解到不能分解，他不做能和排序
 *                 8   4    5   7   1   3   6   2
 *
 *     治：将每个子数组进行排序
 *
 *
 *
 *     1）将数组划分成2部分，左边部分和右边部分
 *     2） 先将左边部分排序，然后将右边部分排序
 *     3） 将左右边排序号的数据写入到一个辅助空间中，让其整体排序
 *     4） 将整体排好序的数据拷贝到原始数组中
 *     时间复杂度O(N*logN)   额外空间复杂度O(N)
 */
public class MegerSort2 {
    public static void main(String[] args) {
        sort(SortConstants.sortArr);
        System.out.println(Arrays.toString(SortConstants.sortArr));
    }
    public static void sort(int arr[]){
        int temp[]=new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }



    //分+和的方法
    private static void sort(int[] arr,int left,int right,int[] temp){
        if(left!=right){
            int mid=left+((right-left)>>1); //获取中间位置
            //向左递归进行分
            sort(arr,left,mid,temp);  //左边排序
            //向右递归进行分
            sort(arr,mid+1,right,temp);//右边排序
            merge(arr,left,mid,right,temp);//将2个有序子数组合并
        }
    }

    /**
     * 合并过程
     * @param arr  原始数组
     * @param left 左边序列的索引
     * @param mid  中间索引
     * @param right  右边索引
     * @param temp
     */
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left; //左指针序列
        int j=mid+1; //右指针序列
        int t=0;  //临时指针序列
        //指标如果没有越界，则将子数组中更小的数据放到临时数组中
        while(i<=mid && j<=right){
            temp[t++]=arr[i]<=arr[j]? arr[i++]: arr[j++];
        }
        //这个循环和下面的那个循环只会有一个进入
        //直接将剩余的数据拷贝到临时开辟的数组中
        //表示左边的数组中数据还有剩余
        while(i<=mid){
            temp[t++] = arr[i++];
        }
        //表示右边边的数组中数据还有剩余
        while(j<=right){
            temp[t++] = arr[j++];
        }

        t=0;

        //数据拷贝回原始数组
        while (left<=right){
            arr[left++]=temp[t++];
        }
    }
}
